#include<bits/stdc++.h>
using namespace std;
class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        int n=s.size();
        unordered_map<string,int>m;
        for(auto&ch:wordDict)m[ch]++;
        vector<bool>dp(n,false);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(j==0) 
                {
                    if(m[s.substr(0,i+1)])
                    {
                        dp[i]=true;
                        break;
                    }
                    continue;
                }
                if(dp[j-1]==true&&m[s.substr(j,i-j+1)])
                {
                    dp[i]=true;
                    break;
                }
            }
            printf("[%d]:%d\n",i,dp[i]);
        }
        return dp[n-1];
    }
};